#ifndef __BINARTREE__HPP_
#define __BINARTREE__HPP_
#include <iostream>
#include "LinkQueue.hpp"

template <typename T>
class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();
    // 插入
    void Insert(const T &element);

    // 按值删除
    void Remove(const T &element);

    // 按值查找
    T *FindByElement(const T &element);

    void show();

private:
    struct Node
    {
        Node(const T &data) : data(data)
        {
            left = right = nullptr;
        }
        T data;
        Node *left;
        Node *right;
    };

    Node *InsertNode(Node *node, const T &element);

    Node *RemoveNode(Node *node, const T &element);
    void FreeNode(Node *node);
    void PreTravel(Node *node);
    void MidTravel(Node *node);
    void BackTravel(Node *node);
    void HeightTravel(Node *node);

    Node *GetMinNode(Node *node);
    T *FindElement(Node *node, const T &element);

    // 右旋
    Node *RotateRight(Node *node);
    // 左旋
    Node *RotateLeft(Node *node);
    // 左右旋
    Node *RotateLeftRight(Node *node);
    // 右左旋
    Node *RotateRightLeft(Node *node);

    int GetNodeHight(Node *node);
    int LRDevition(Node *node);
    Node *root;
};

template <typename T>
BinaryTree<T>::BinaryTree()
{
    root = nullptr;
}

template <typename T>
inline BinaryTree<T>::~BinaryTree()
{
    FreeNode(root);
}

template <typename T>
void BinaryTree<T>::Insert(const T &element)
{
    root = InsertNode(root, element);
}

template <class T>
void BinaryTree<T>::FreeNode(BinaryTree<T>::Node *node)
{
    // 终止条件
    if (node == nullptr)
        return;
    FreeNode(node->left);
    FreeNode(node->right);
    delete node;
}

template <typename T>
void BinaryTree<T>::Remove(const T &element)
{
    root = RemoveNode(root, element);
}

template <typename T>
T *BinaryTree<T>::FindByElement(const T &element)
{
    return FindElement(root, element);
}

template <typename T>
void BinaryTree<T>::show()
{
    std::cout << "前: ";
    PreTravel(root);
    std::cout << std::endl;
    std::cout << "中: ";
    MidTravel(root);
    std::cout << std::endl;
    std::cout << "后: ";
    BackTravel(root);
    std::cout << std::endl;
    std::cout << "层: ";
    HeightTravel(root);
}

template <typename T>
typename BinaryTree<T>::Node *BinaryTree<T>::InsertNode(BinaryTree<T>::Node *node, const T &element)
{
    // 如果直接找到要插入的位置
    if (node == nullptr)
        return new Node(element);
    // 要插入的元素已经存在 二叉排序树不放置相同数据
    if (node->data == element)
        return node;
    if (node->data > element)
    {
        // 递归插入左子树
        node->left = InsertNode(node->left, element);
        if (LRDevition(node) >= 2)
        {
            if (element < node->left->data)
                RotateRight(node);
            else
            {
                RotateLeftRight(node);
            }
        }
    }
    else
    {
        // 递归插入右子树
        node->right = InsertNode(node->right, element);
        if (LRDevition(node) <= -2)
        {
            if (element > node->right->data)
                RotateLeft(node);
            else
            {
                RotateRightLeft(node);
            }
        }
    }
    return node;
}

template <typename T>
typename BinaryTree<T>::Node *BinaryTree<T>::RemoveNode(BinaryTree<T>::Node *node, const T &element)
{
    if (node == nullptr)
        return nullptr;

    if (node->data < element)
    {
        node->right = RemoveNode(node->right, element);
    }
    else if (node->data > element)
    {
        node->left = RemoveNode(node->left, element);
    }
    else
    {
        // 叶子结点
        if (node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        // 有两个孩子
        else if (node->left != nullptr && node->right != nullptr)
        {
            // 找到右子树中的最小值
            Node *minNode = GetMinNode(node->right);
            node->data = minNode->data; // 把最小值的结点数值给要被删除的结点
            // 删除右子树中的最小结点
            node->right = RemoveNode(node->right, minNode->data);
        }
        // 有一个孩子
        else
        {
            // 把子树接给被删掉的树的父树
            Node *child = node->left ? node->left : node->right;
            delete node;
            node = child;
        }
    }
    if (LRDevition(node) >= 2)
    {
        if (LRDevition(node->left) > 0)
        {
            node = RotateRight(node);
        }
        else
        {
            node = RotateLeftRight(node);
        }
    }
    else if (LRDevition(node) <= -2)
    {
        if (LRDevition(node->right) < 0)
        {
            node = RotateLeft(node);
        }
        else
        {
            node = RotateRightLeft(node);
        }
    }

    return node;
}

template <typename T>
void BinaryTree<T>::PreTravel(BinaryTree<T>::Node *node)
{
    if (node == nullptr)
        return;

    std::cout << node->data << " ";
    PreTravel(node->left);
    PreTravel(node->right);
}

template <typename T>
void BinaryTree<T>::MidTravel(Node *node)
{
    if (node == nullptr)
        return;

    MidTravel(node->left);
    std::cout << node->data << " ";
    MidTravel(node->right);
}

template <typename T>
void BinaryTree<T>::BackTravel(Node *node)
{
    if (node == nullptr)
        return;

    BackTravel(node->left);
    BackTravel(node->right);
    std::cout << node->data << " ";
}

template <typename T>
void BinaryTree<T>::HeightTravel(Node *node)
{
    LinkQueque<Node *> q;
    q.Push(root);
    while (!q.IsEmpty())
    {
        Node *node = (Node *)*q.GetFront();
        std::cout << node->data << " ";
        if (node->left)
            q.Push(node->left);
        if (node->right)
            q.Push(node->right);
        q.Pop();
    }
    std::cout << std::endl;
}

template <typename T>
typename BinaryTree<T>::Node *BinaryTree<T>::GetMinNode(Node *node)
{
    while (node->left != nullptr)
    {
        node = node->left;
    }
    return node;
}

template <typename T>
T *BinaryTree<T>::FindElement(BinaryTree<T>::Node *node, const T &element)
{
    if (node == nullptr)
    {
        return nullptr;
    }
    if (element == node->data)
    {
        return &node->data;
    }
    else if (element < node->data)
    {
        return FindElement(node->left, element);
    }
    else
    {
        return FindElement(node->right, element);
    }
}

template <typename T>
typename BinaryTree<T>::Node *BinaryTree<T>::RotateRight(Node *node)
{
    Node *p = node->left;
    node->left = p->right;
    p->right = node;
    return p; // 返回新的根
}

template <typename T>
typename BinaryTree<T>::Node *BinaryTree<T>::RotateLeft(Node *node)
{
    Node *p = node->right;
    node->right = p->left;
    p->left = node;
    return p;
}

template <typename T>
typename BinaryTree<T>::Node *BinaryTree<T>::RotateLeftRight(Node *node)
{
    // 左子树左旋
    node->left = RotateLeft(node->left);
    return RotateRight(node); // 整体右旋
}

template <typename T>
typename BinaryTree<T>::Node *BinaryTree<T>::RotateRightLeft(Node *node)
{
    node->right = RotateRight(node->right);
    return RotateLeft(node);
}

template <typename T>
int BinaryTree<T>::GetNodeHight(Node *node)
{
    if (node == nullptr)
        return 0;

    int leftHight = GetNodeHight(node->left);

    int rightHight = GetNodeHight(node->right);

    return (leftHight > rightHight ? leftHight : rightHight);
}

template <typename T>
int BinaryTree<T>::LRDevition(Node *node)
{
    if (node == nullptr)
        return 0;
    return GetNodeHight(node->left) - GetNodeHight(node->right);
}

#endif